// https://leetcode-cn.com/problems/perfect-squares/
// 279. Perfect Squres
// Given an integer n, return the least number of perfect square numbers that sum to
// n.
function numSquares(n: number): number {
    const dp = new Array(n + 1).fill(Infinity);
    dp[0] = 0;

    for (let i = 1; i <= n; i++) {
        for (let j = 1; j * j <= i; j++) {
            dp[i] = Math.min(dp[i], dp[i - j * j] + 1);
        }
    }

    console.log(dp);

    return dp[n];
}

numSquares(20);
